package day01;

public class MyHashMap<K, V> {
    private Node<K, V>[] table;
    private int size;

    private class Node<K, V>{
        K key;
        V value;
        Node<K, V> next;
        public Node(K key, V value){
            this.key = key;
            this.value = value;
        }
    }

    public V put(K key, V value){
        if(size == 0){
            table = new Node[16];
        }
        //根据key计算出存储位置(取余数)
        // java HashMap 为了让高16位和低16位共同影响散列存储位置,
        // 将 hashCode 的高16位移动到低16位, 然后异或拼接为一个数, 再取余数
        // 目的是扩大数据的分散度, 提升查询性能
        // 异或规则: 相同为0 不同为1
        // h = key.hashCode()
        // h          01111101 00010010 00001001 00110101
        // h>>>16     00000000 00000000 01111101 00010010
        // 异或 ^      01111101 00010010 01110100 00100111
        // & 1111                                    0111
        //将数据存储到 table 中
        //先检查位置上是否有元素
        int index = hash(key);
        if (table[index]==null) {
            table[hash(key)] = new Node<>(key, value);
            size++;
            return null;
        }else{
            //已经有元素了!
            //- 如果key一样就替换
            //- 如果key不同就链表节点添加上
            Node<K,V> node = table[index];
            while (! key.equals(node.key)){
                if (node.next == null){
                    node.next = new Node<>(key, value);
                    size++;
                    return null;
                }
                node = node.next;
            }
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
    }
    private int hash(K key){
        int h = key.hashCode();
        return (h ^ (h >>> 16)) & (table.length-1);
    }
    public V get(K key){
        Node<K, V> node = table[hash(key)];
        while (! key.equals(node.key)){
            if (node.next == null){
                return null;
            }
            node = node.next;
        }
        return node.value;
    }
}
